// 哈夫曼编码
#include <iostream>
#include <tchar.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX 100

int L;
int s[8];
float temp;
double H = 0;
double R;
typedef struct //节点
{
    int weight;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树

typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表

void SelectMinNode(HuffmanTree &HT, int m, int &i1, int &i2) //找出权值最小的两个节点对应的数组下标
{
    HuffmanTree p = HT;
    int s1, s2;
    s1 = s2 = MAX;
    i1 = i2 = 1;
    for (int i = 1; i <= m; i++)
    {
        if (!(p + i)->parent)
        {
            if ((p + i)->weight < s1)
            {
                i2 = i;
                s1 = (p + i)->weight;
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (!(p + i)->parent && i != i2)
        {
            if ((p + i)->weight < s2)
            {
                i1 = i;
                s2 = (p + i)->weight;
            }
        }
    }
}

void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制
{
    char *c1, *c2;
    c1 = p;
    while (q[start] != '\0')
    {
        *c1 = q[start];
        c1++;
        start++;
    }
    *c1 = q[start]; //别忘了将‘\n’复制过来
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数

    int i, i1, i2, m;
    HuffmanTree p;
    if (n <= 1)
        return;
    m = 2 * n - 1;                                      //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //数组首元素不使用，故多分配一个空间
    p = HT + 1;
    for (i = 1; i <= n; ++i, ++p, ++w) //n个叶子节点初始化
    {
        p->weight = *w;
        p->lchild = 0;
        p->rchild = 0;
        p->parent = 0;
    }
    for (; i <= m; ++i, ++p) //非叶子节点初始化
    {
        p->weight = 0;
        p->lchild = 0;
        p->rchild = 0;
        p->parent = 0;
    }
    for (i = n + 1; i <= m; ++i) //对非叶子节点重新计算
    {
        SelectMinNode(HT, i - 1, i1, i2);
        HT[i1].parent = i;
        HT[i2].parent = i;
        HT[i].lchild = i1;
        HT[i].rchild = i2;
        HT[i].weight = HT[i1].weight + HT[i2].weight;
    }
    //从叶子节点到根节点逆向求每个字符的赫夫曼编码
    char *cd;
    int start, c, f;

    HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个字符编码的头指针向量
    cd = (char *)malloc(n * sizeof(char));              //临时变量，用于存储当前叶子节点的赫夫曼编码
    cd[n - 1] = '\0';                                   //编码结束符
    //printf("	码字长度为:	");
    for (int i = 1; i <= n; i++) //逐个字符求哈夫曼编码
    {
        start = n - 1;                                                 //编码结束符位置
        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) //从叶子到跟逆向求编码
        {
            if (HT[f].lchild == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
        }
        HC[i] = (char *)malloc((n - start) * sizeof(char)); //为第i个字符编码分配空间
        StrCopy(HC[i], cd, start);                          //将存储的编码copy给HC的第i个数组
        L = strlen(HC[i]);                                  //求各个码字码长
        //printf("	%d", L);
        s[i] = L;
    }
    printf("\n");
    free(cd);
}

void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, float *b, int n) //打印各节点的赫夫曼编码
{
    int L;
    HuffmanCode p;
    printf("	概率:	权值:	码字:	码长:\n\n");
    for (int i = 1; i <= n; i++)
    {
        p = HC;
        printf("	%.2f	", b[i - 1]);
        printf("%d	", HT[i]);
        while (*p[i] != '\0')
        {
            printf("%c", *p[i]);
            p[i]++;
        }
        printf("	%d	", s[i]);
        printf("\n");
    }
    printf("\n");
}

int main()
{
    int n = 7; //权值数
    float K = 0;
    HuffmanTree HT;
    HuffmanCode HC;
    /*float p[5] = {0.4,0.2,0.2,0.1,0.1};
	int a[5] = {4,2,2,1,1};*/
    float p[7] = {0.2, 0.19, 0.18, 0.17, 0.15, 0.1, 0.01};
    int a[7] = {20, 19, 18, 17, 15, 10, 1}; //信号源的概率分布，即P={p0, p1,…, pK-1}
    HuffmanCoding(HT, HC, a, n);
    PrintHuffmanCode(HT, HC, p, n);
    for (int i = 0; i < n; i++)
    {
        temp = (float)(a[i] * 0.01);       //权值转化为信源概率
        K = K + (float)s[i + 1] * temp;    //求平均码长
        H = H + (temp * (log2(1 / temp))); //求信源熵
    }
    R = H / K; //求编码效率
    printf("\n	平均码长为:	");
    printf("K = %.4f", K);
    printf("\n	信源熵为:	");
    printf("H = %.4lf	", H);
    printf("\n	编码效率为:	");
    printf("R = %.4lf	\n\n\n", R);
    return 0;
}
